package recursion.nowcoder.easy;

/**
 * @author bruin_du
 * @description 跳台阶扩展问题
 * https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387
 * @date 2022/5/25 15:38
 **/
public class JumpFloorII {
    public int jumpFloorII (int number) {
        //递归法
        recursion(number);

        iteration(number);

        return regularity(number);
    }

    private int regularity(int number) {
        return (int)Math.pow(2,number - 1);
    }

    private int iteration(int number) {
        int sum = 1,prev = 1;
        for (int i = 1; i < number; i++) {
            sum += prev;
            prev = sum;
        }
        return sum;
    }

    private int recursion(int number) {
        if(number == 2) return 2;
        if(number == 1 || number == 0) return 1;
        if(number < 0) return 0;
        int sum = 0;
        for(int i = 1; i <= number;i++){
            sum += jumpFloorII(number - i);
        }
        return sum;
    }
}
